#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
@File Name: 带键值对的树_btreevals.py
@Author: LT
@Date: 2021/9/29 14:30
# -----------------------------------------------------------------------------------------------------
@Description: 
同时保存键和它对应的值（甚至多个值）
# -----------------------------------------------------------------------------------------------------
"""


class KeyedBinaryTree:
    """该类是总的树管理，只实例化生成一次"""
    def __init__(self):
        self.tree = EmptyNode()

    def lookup(self, key):
        return self.tree.lookup(key)

    def insert(self, key, value):
        """如果是以键值对的形式传入的话，该以什么作为依据排序呢？我觉得该以键为基准"""
        self.tree = self.tree.insert(key, value)

    def __repr__(self):
        return repr(self.tree)
        # return self.tree 会出错的


class EmptyNode:
    def __repr__(self):
        return "*"

    def lookup(self, key):
        """坚定面向对象OOP，叶子节点你咋查都查不到，得返回False"""
        return False, f"has no this key:{key}"

    def insert(self, key, value):
        return BinaryNode(self, key, value, self)


class BinaryNode:
    def __init__(self, left, key, value, right):
        self.left = left
        self.right = right
        self.key = key
        self.value = value

    def lookup(self, key):
        """递归不能没有return或者赋值啊"""
        if key == self.key:
            return True, f"value is {self.value}"
        elif key > self.key:
            return self.right.lookup(key)
        else:
            return self.left.lookup(key)

    def insert(self, key, value):
        """不需要判断是否已有该键，采用不等式就可规避已有的键的插入"""
        if self.key > key:
            self.left = self.left.insert(key, value)
        elif self.key < key:
            self.right = self.right.insert(key, value)
        return self

    def __repr__(self):
        return '( %s, %s=%s, %s )' % (repr(self.left), repr(self.key), repr(self.value), repr(self.right))


if __name__ == '__main__':
    t = KeyedBinaryTree()
    for key, val in [("bbb", 1), ("aaa", 2), ("ccc", 3)]:
        t.insert(key, val)
    print(t)
    print(t.lookup("aaa"), t.lookup("ccc"))
    t.insert("ddd", 4)
    t.insert("aaa", 5)
    print(t)
    print(t.lookup("kk"))
    pass
